\section{Conclusion and open questions}
\label{sec:token.open}

In this paper, we studied the power of token-forwarding algorithms for
gossip in dynamic networks. We showed a lower bound of $\Omega(nk/\log
n)$ rounds for any online token forwarding algorithm against a strong
adversary; our bound matches the known upper bound of $O(nk)$ up to a
logarithmic factor.  We note that our lower bound also extends to
randomized algorithms if the adversary is allowed to be adaptive; that
is, the adversary is allowed to make its decision in each step with
knowledge of the random coin tosses made by the algorithm in that step
(but without knowledge of the randomness used in future steps).  This
leaves us with an important open question: what is the complexity of
randomized online token-forwarding algorithms against a weak adversary
that is unaware of the randomness used by the algorithm in each round?
Furthermore, for small token sizes (e.g., $O(\log n)$ bits) even the
best (randomized) online algorithm we know based on network coding
takes $O(nk/\log n)$ rounds~\cite{haeupler+k:dynamic}.  In contrast,
we show that in the offline setting there exist centralized
token-forwarding algorithms that run in $O(n^{1.5}\sqrt{\log n})$
time.  An interesting open problem is to obtain tight bounds on
offline token-forwarding algorithms.


